package algorithm.middle;

/**
 * 给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位数字。
 */
public class FindNthDigit400 {


    /**
     * 1-9 ->9
     * 10-99 ->90 * 2
     * 100-999 -> 900 * 3
     * 1000-9999 -> 9000
     * 10000-99999 -> 90000
     */
    public static int findNthDigit(int n) {
        if (n <= 9) return n;
        int i = 1;
        long h = 9;
        long ten = 1;
        while (n > h) {
            n = (int) (n-h);
            i++;
            ten = ten * 10;
            h = 9 * ten  * i;
        }
        int cur = (int) ((n - 1) / i + ten);
        int index = (n - 1) % i;
        char c = (cur + "").charAt(index);
        return c - 48;

    }

    public static void main(String[] args) {
        System.out.println(findNthDigit(1000000000));
        System.out.println(findNthDigit2(1000000000));
    }

    public static int findNthDigit2(int n) {
        if (n <= 9) return n;
        int i = 1;
        int h = 9;
        int ten = 1;
        for (; n > 9 * Math.pow(10, i - 1) * i; i++) {
            n = (int) (n - 9 * Math.pow(10, i - 1) * i);
        }
        int cur = (int) ((n - 1) / i + Math.pow(10, i - 1));
        int index = (n - 1) % i;
        char c = (cur + "").charAt(index);
        return c - 48;

    }

}
